package com.wfm.niuke.huisu;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class P剑指Offer38字符串的排列 {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    Set<String> res = new HashSet<>();
    StringBuilder path = new StringBuilder();

    public String[] permutation(String s) {
        if(s.length()==0) return  new String[0];
        boolean[] visited = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            dfs(s,i,s.length(),visited);
        }
        String[] r = res.toArray(new String[res.size()]);
        return r;
    }
    void dfs(String s,int i,int n,boolean[] visited){
//        if(i>=s.length()) return;
        if(visited[i]) return;
        path.append(s.charAt(i));
        visited[i]=true;
        if(path.length()==n){
            res.add(path.toString());
        }
        for (int j = 0; j < s.length(); j++) {
            dfs(s,j,n,visited);
        }
        path.deleteCharAt(path.length()-1);
        visited[i]=false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer38字符串的排列().new Solution();
        String[] abcs = solution.permutation("abc");

        System.out.println(Arrays.toString(abcs));
    }
}